#ifndef __DALELIB_GENETICALGORITHM_H__
#define __DALELIB_GENETICALGORITHM_H__

#include <dalelib/graphics.h>
#include <dalelib/utils/daleassert.h>
#include <vector>
#include <fstream>
using namespace std;

namespace dalelib
{

/******************************************************************
	Class: Genotype
	Derive your own from this class
	or copy DefaultGenotype found at the bottom of this file
 ******************************************************************/
class Genotype
{
protected:

	float _fitness;

public:

	Genotype();
	virtual ~Genotype();
	float& getFitness() { return _fitness; }
//	virtual void crossover(Genotype& _Parent1,Genotype& _Parent2);
	virtual void crossover(void* _Parent1,void* _Parent2);
	virtual void mutate(const float _MutationRate);
	virtual void createRandom(const int _Size);
	virtual void validate();
	virtual void save(const string _FileName);
	virtual void load(const string _FileName);

};


//*******************************************************************
template<class T>
class GeneticAlgorithm
{
private:

	float _mutation_rate;
	vector<T> _gene_pool[2];
	int _db_gene_pool; // double buffer
	bool _range;
	bool _wrap;
	float _elitism;
	struct GenerationData { float _min,_max,_av; GenerationData():_min(999999.f),_max(-999999.f),_av(0.f){} };
	vector<GenerationData> _generation_data;

public:

	GeneticAlgorithm()
		: _db_gene_pool(0)
		, _mutation_rate(0.1f)
		, _range(9999999)
		, _wrap(true)
		, _elitism(0.1f)
	{ }

	~GeneticAlgorithm() { }

	T& getIndividual(const int _Index) { return _gene_pool[_db_gene_pool][_Index]; }
	void setMutationRate(const float _MutationRate) { _mutation_rate = _MutationRate; }
	void setElitism(const float _Elitism) { _elitism = _Elitism; }

	int& getRange() { return _range; }
	bool& getWrap() { return _wrap; }

	void initialisePopulation(const int _Size,const int _Length)
	{
		_range = _Size;
		_gene_pool[0].resize(_Size);
		_gene_pool[1].resize(_Size);
		for(int i=0; i<_Size; ++i)
		{
			_gene_pool[0][i].createRandom(_Length);
			_gene_pool[1][i].createRandom(_Length);
		}
	}

	int rouletteSelection(const int _Buffer,const int _Index)
	{
		int start = _Index-_range;
		int end = _Index+_range;
		if(_wrap)
		{
			if(start<0) start += _gene_pool[_Buffer].size();
			if(end>=(int)_gene_pool[_Buffer].size()) end -= _gene_pool[_Buffer].size();
		}
		else
		{
			if(start<0) start = 0;
			if(end>=(int)_gene_pool[_Buffer].size()) end = _gene_pool[_Buffer].size()-1;
		}

		float total_fitness = 0.f;
		for(int i=start; i<=end; ++i)
		{
			total_fitness += _gene_pool[_Buffer][i].getFitness();
		}

		float rand_fitness = RAND*total_fitness;
		float cumulative_fitness = 0.f;
		int chosen_index = 0;
		for(int i=start; i<=end; ++i)
		{
			cumulative_fitness += _gene_pool[_Buffer][i].getFitness();
			if( cumulative_fitness>=rand_fitness )
			{
				chosen_index = i;
				break;
			}
		}
		return chosen_index;
	}

	void breed()
	{

		int old_generation = _db_gene_pool;
		int new_generation = (_db_gene_pool+1)%2;

		// *** store generation data ***
		GenerationData gd;
		for(unsigned int i=0; i<_gene_pool[old_generation].size(); ++i)
		{
			const float f = _gene_pool[old_generation][i].getFitness();
			if(f<gd._min) gd._min = f;
			if(f>gd._max) gd._max = f;
			gd._av += f;
		}
		gd._av /= _gene_pool[old_generation].size();
		_generation_data.push_back(gd);

		// *** created sorted list for elitism ***
		vector<int> sorted(_gene_pool[old_generation].size());
		for(unsigned int i=0; i<_gene_pool[old_generation].size(); ++i) sorted[i] = i;
		for(unsigned int i=0; i<_gene_pool[old_generation].size()-1; ++i)
		{
			for(unsigned int j=i+1; j<_gene_pool[old_generation].size(); ++j)
			{
				if(_gene_pool[old_generation][sorted[i]].getFitness()<_gene_pool[old_generation][sorted[j]].getFitness())
				{
					int temp = sorted[i]; sorted[i] = sorted[j]; sorted[j] = temp; // swap
				}
			}
		}

		for(unsigned int i=0; i<_gene_pool[new_generation].size(); ++i)
		{
			if( float(i)/(_gene_pool[new_generation].size()-1)<_elitism )
			{
				void* p1 = &(_gene_pool[old_generation][sorted[i]]);
				void* p2 = &(_gene_pool[old_generation][sorted[i]]);
				_gene_pool[new_generation][i].crossover(p1,p2);
			}
			else
			{
				void* p1 = &(_gene_pool[old_generation][rouletteSelection(old_generation,i)]);
				void* p2 = &(_gene_pool[old_generation][rouletteSelection(old_generation,i)]);
				_gene_pool[new_generation][i].crossover(p1,p2);
				_gene_pool[new_generation][i].mutate(_mutation_rate);
			}
		}
		_db_gene_pool = new_generation;
	}

	void savePopulation(const string _Path)
	{
		string path = _Path;
		if(path[path.size()-1]!='/') path += string("/");
		char name[256];
		for(unsigned int i=0; i<_gene_pool[_db_gene_pool].size(); ++i)
		{
			sprintf(name,"%sgenotype%.5d.txt",path.c_str(),i);
			// todo
		}
	}

	void saveGenerationData(const string _FileName,const string _Delimiter=", ")
	{
		ofstream myfile;
		myfile.open(_FileName.c_str());
		myfile << "Generation,Minimum,Maximum,Average," << endl;
		for(unsigned int i=0; i<_generation_data.size(); ++i)
		{
			myfile << i                        << _Delimiter;
			myfile << _generation_data[i]._min << _Delimiter;
			myfile << _generation_data[i]._max << _Delimiter;
			myfile << _generation_data[i]._av  << _Delimiter << endl;
		}
		myfile.close();
	}

	int getFittestIndex()
	{
		int fittest_index = 0;
		float fittest_value = -999999.f;
		for(unsigned int i=0; i<_gene_pool[_db_gene_pool].size(); ++i)
		{
			const float f = _gene_pool[_db_gene_pool][i].getFitness();
			if( f>fittest_value )
			{
				fittest_value = f;
				fittest_index = i;
			}
		}
		return fittest_index;
	}

};

//******************************************************************
class DefaultGenotype : public Genotype
{
private:

	vector<float> _dna;
	float _lower_limit;
	float _upper_limit;
	float _mutation_size;

public:

	DefaultGenotype();
	~DefaultGenotype();

	float& getLowerLimit() { return _lower_limit; }
	float& getUpperLimit() { return _upper_limit; }
	float& getMutationSize() { return _mutation_size; }

	vector<float>& getDNA() { return _dna; }

	void crossover(void* _Parent1,void* _Parent2);
	void mutate(const float _MutationRate);
	void createRandom(const int _Length);
	void validate();
	void save(const string _FileName);
	void load(const string _FileName);

};

typedef GeneticAlgorithm<DefaultGenotype> StandardGA;

} // namespace dalelib

#endif // __DALELIB_GENETICALGORITHM_H__
